/**
 * 原理：将元素插入到已经存在的有序数组中去
   实现过程：遍历数组，将当前索引位置的元素插入到此索引位置之前的有序数组中去
   理解：假如现在遍历到的索引位置为n，则[0...n-1]已经是有数组了，对于n索引位置的元素x，遍历[0...n-1]，找到x应该所在的位置p，将[p...n-1]的元素逐个向后移动，变成[p+1...n],然后将x放到p位置上。
   难点：p=0的情况的处理

   时间复杂度：最好O(n),最坏O(n*n)
   空间：O(1)
   稳定排序
 * @param {*} arr 
 * @returns 
 */
function directInsertionSort(arr) {
  if (!Array.isArray(arr)) throw new TypeError("argument must be a array");
  const _newArr = arr;
  const len = _newArr.length;
  if (len < 2) return _newArr;

  for (let i = 0; i < len; i++) {
    // 当前要插入的元素
    const current = _newArr[i];

    // 对前面已经排好的进行位置替换
    // j是已经排好的索引
    let j = i - 1;
    while (j >= 0 && _newArr[j] > current) {
      //   如果当前要插入的小于当前j位置的，那么将当前j位置的往后移动
      _newArr[j + 1] = _newArr[j];

      j -= 1;
    }

    // 最后j小0或者j位置的值小于current，将当前current值插入到找到的j的前面一个位置
    _newArr[j + 1] = current;
  }

  return _newArr;
}

// egg:

const arr = [1, 3, 5, 4, 6, 8, 2, 7];
console.log("[ arr ] >", directInsertionSort(arr));
